package com.gitee.feizns.explore.data_structure.sort;

import java.util.Arrays;

/**
 * @author feizns
 * @since 2019/12/31
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{ 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
        mergeSort2(arr);
        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(Arrays.copyOfRange(arr, 0, 3)));
//        int[] arr = new int[10000000];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int)(Math.random() * 10000000);
//        }
//        mergeSort(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if ( l >= r ) return;

        int mid = (l + r) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);

        if ( arr[mid] > arr[mid + 1] )
            merge(arr, l, mid, r);
    }

//    public static void merge(int[] arr, int l, int m, int r) {
//        int size = r - l + 1;
//        int[] ret = new int[size];
//        int oL = l;
//        int index = 0;
//        int k = m + 1;
//        while ( index < size ) {
//            if ( l > m )
//                ret[index++] = arr[k++];
//            else if ( k > r )
//                ret[index++] = arr[l++];
//            else if ( arr[l] < arr[k] )
//                ret[index++] = arr[l++];
//            else
//                ret[index++] = arr[k++];
//        }
//        replace(arr, oL, ret);
//    }

    public static void merge(int[] arr, int l, int m, int r) {
        int[] tmp = Arrays.copyOfRange(arr, l, r + 1);
        int tl = 0;
        int ml = m - l;
        int rl = ml + 1;
        int k = l;
        while ( k < r + 1 ) {
            if ( tl > ml ) {
                arr[k++] = tmp[rl++];
            } else if ( rl > tmp.length - 1 ) {
                arr[k++] = tmp[tl++];
            } else if ( tmp[tl] < tmp[rl] ) {
                arr[k++] = tmp[tl++];
            } else {
                arr[k++] = tmp[rl++];
            }
        }
    }

    private static int[] copy(int[] arr, int l, int r) {
        return Arrays.copyOfRange(arr, l, r + 1);
    }

//    public static void mergeOriginal(int[] arr, int l, int m, int r) {
//        int index = l;
//        int k = m + 1;
//        while ( index <= r ) {
//            if ( l > m || k > r )
//                arr[index++] = arr[k++];
//            else if ( arr[l] < arr[k] ) {
//                index++;
//                l++;
//            } else {
//                int tmp = arr[l++];
//                arr[index++] = arr[k];
//                arr[k] = tmp;
//            }
//        }
//    }

    private static void replace(int[] original, int l, int[] arr) {
        for (int i = 0; i < arr.length; i++)
            original[l++] = arr[i];
    }

    private static void mergeSort2(int[] arr) {
        for (int i = 1; i < arr.length; i += i) {
            for (int j = 0; j + i < arr.length; j += (2*i)) {
                merge(arr, j, j + i - 1, Math.min(arr.length - 1, j + i + i - 1));
            }
        }
    }

//    private static void linkSort2(int[] arr) {
//        for (int i = 1; i < arr.length; i += i) {
//            for (int j = 0; j + i < arr.length; j += (2*i)) {
//                merge(arr, j, j + i - 1, Math.min(arr.length - 1, j + i + i - 1));
//            }
//        }
//    }

}
